#include <stdio.h>
#include <stdlib.h>

typedef int HElemSet;
typedef struct LeftistHeapNode *LeftistHeap;
struct LeftistHeapNode {
    HElemSet key; /* 数据元素 */
    int npl; /* 左堆的npl值 */
    LeftistHeap left; /* 左子树 */
    LeftistHeap right; /* 右子树 */
};

/* 算法6-9：左堆的合并操作 LeftistMerge(h1, h2) */
LeftistHeap LeftistMerge(LeftistHeap h1, LeftistHeap h2) {
    LeftistHeap tmp;
    int s1, s2;

    if (h1 == NULL) {
        return h2;
    }
    if (h2 == NULL) {
        return h1;
    }
    if (h1->key > h2->key) {
        return LeftistMerge(h2,
                            h1); /* 保证第一个堆的根结点是较小的那个 */
    }
    /* 现在 h1->key <= h2->key */
    if (h1->left == NULL) { /* 如果左子树为空，则h1肯定是单结点树 */
        h1->left = h2;
    } else {
        h1->right = LeftistMerge(h1->right, h2);
        if (h1->left->npl < h1->right->npl) { /* 保证左堆性质 */
            tmp = h1->left;
            h1->left = h1->right;
            h1->right = tmp;
        }
        h1->npl = h1->right->npl + 1; /* 右子树的npl值一定比较小 */
    }
    return h1;
}
/* 算法6-9 结束 */

LeftistHeap CreateNode() {
    /* 创建单个结点 */
    LeftistHeap h;

    h = (LeftistHeap)malloc(sizeof(struct LeftistHeapNode));
    scanf("%d", &h->key);
    h->npl = 1;
    h->left = NULL;
    h->right = NULL;
    return h;
}

LeftistHeap CreateHeap() {
    /* 创建左堆 */
    LeftistHeap h1, h2;
    int n, i;

    scanf("%d", &n);
    h1 = CreateNode();
    for (i = 1; i < n; i++) {
        h2 = CreateNode();
        h1 = LeftistMerge(h1, h2); /* 将每个结点顺次并入左堆 */
    }
    return h1;
}

void Visit(LeftistHeap tree) {
    /* 输出键值和空路径长度 */
    printf("%d:%d\n", tree->key, tree->npl);
}

void PreOrder(LeftistHeap tree) {
    /* 前序遍历 */
    if (tree != NULL) {
        Visit(tree);
        PreOrder(tree->left);
        PreOrder(tree->right);
    }
}

void InOrder(LeftistHeap tree) {
    /* 中序遍历 */
    if (tree != NULL) {
        InOrder(tree->left);
        Visit(tree);
        InOrder(tree->right);
    }
}

int main(void) {
    LeftistHeap h1, h2;

    h1 = CreateHeap();
    h2 = CreateHeap();
    h1 = LeftistMerge(h1, h2);
    PreOrder(h1);
    InOrder(h1);

    return 0;
}